What is handshaking lemma?

The Handshaking Lemma is a basic principle in graph theory that states that the sum of the degrees of all the vertices in a graph is equal to twice the number of edges in the graph.

In other words, if we add up the number of connections or edges at each vertex in a graph, the total will be twice the number of edges in the graph. This is because every edge connects two vertices, so each edge contributes to the degree of two vertices.

The Handshaking Lemma is a fundamental result that is used in various applications of graph theory, such as in determining properties of networks, calculating the number of cycles in a graph, or finding the number of vertices of odd degree in a graph.

The Handshaking Lemma is also known as the Handshaking Theorem or the Degree-Sum Formula. It is a simple yet powerful tool that helps to analyze and understand the structure of graphs.